package 合并两个有序数组;

public class test {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
        for (int i = 0; i < m; i++) {
            int temp;
            if (nums1[i] > nums1[m]) {
                temp = nums1[i];
                nums1[i] = nums1[m];
                nums1[m] = temp;
                method1(nums1, m);
            }
        }
    }

    public static void method1(int[] nums1, int m) {
        int temp;
        for (int i = m; i < nums1.length - 1; i++) {
            if (nums1[i + 1] < nums1[i]) {
                temp = nums1[i];
                nums1[i] = nums1[i + 1];
                nums1[i + 1] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 5, 6, 7, 9, 0, 0, 0, 0, 0, 0,};
        int[] b = {2, 4, 8, 10, 13, 14};
//        merge(a,5,b,6);
        //仅适用书上8.5.13一个数组的两个子有序段的情况，改过也不对
        //88图解见下面方法
        method88(a, 5, b, 6);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ",");
        }
    }

    public static void method88(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1, 0, nums1_copy, 0, m);

        //两个指针
        int p1 = 0;
        int p2 = 0;

        int p = 0;
        while ((p1 < m) && (p2 < n)) {
            nums1[p++] = nums1_copy[p1] < nums2[p2] ? nums1_copy[p1++] : nums2[p2++];
        }
        //如果还有剩余元素
        if (p1 < m)
            System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
        if (p2 < n)
            System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
    }

    public void merge0(int[] nums1, int m, int[] nums2, int n) {
        //考虑两个元素
        int p1=0;
        int p2=0;
        int[] sorted=new int[m+n];
        int cur=0;

        while (p1<m||p2<n){
            //边界条件
            if (p1==m){
                cur=nums2[p2];
                p2++;
            }
            else if (p2==n){
                cur=nums1[p1];
                p1++;
            }
            else if (nums1[p1]<nums2[p2]){
                cur=nums1[p1];
                p1++;
            }
            else {
                cur=nums2[p2];
                p2++;
            }
            sorted[p1+p2-1]=cur;
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i]=sorted[i];
        }




    }

}
